|
In coding theory, Kraft's inequality, named after Leon Kraft, gives both a necessary and sufficient condition for the existence of a prefix code〔 for a given set of codeword lengths. Its applications to prefix codes and trees often find use in computer science and information theory. More specifically, Kraft's inequality limits the lengths of codewords in a prefix code: if one takes an exponential of the length of each valid codeword, the resulting set of values must look like a probability mass function, that is, it must have total measure less than or equal to one. Kraft's inequality can be thought of in terms of a constrained budget to be spent on codewords, with shorter codewords being more expensive. * If Kraft's inequality holds with strict inequality, the code has some redundancy. * If Kraft's inequality holds with equality, the code in question is a complete code. * If Kraft's inequality does not hold, the code is not uniquely decodable. Kraft's inequality was published by . However, Kraft's paper discusses only prefix codes, and attributes the analysis leading to the inequality to Raymond Redheffer. The inequality is sometimes also called the Kraft–McMillan theorem after the independent discovery of the result by ; McMillan proves the result for the general case of uniquely decodable codes, and attributes the version for prefix codes to a spoken observation in 1955 by Joseph Leo Doob. == Examples == 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kraft's inequality」の詳細全文を読む スポンサード リンク
|